package cn.edu.jxau.test;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.Queue;

/**
 * Kruskal算法：
 * 
 * 空间复杂度O(E)，所需时间复杂度O(ElogE)
 * @author 付大石
 */
public class Kruskal {

    public static void main(String[] args) {

        UndirectedGraph g = new UndirectedGraph(8);
        g.addEdge(new Edge(4, 5, 0.35));
        g.addEdge(new Edge(4, 7, 0.37));
        g.addEdge(new Edge(5, 7, 0.28));
        g.addEdge(new Edge(0, 7, 0.16));
        g.addEdge(new Edge(1, 5, 0.32));
        g.addEdge(new Edge(0, 4, 0.38));
        g.addEdge(new Edge(2, 3, 0.17));
        g.addEdge(new Edge(1, 7, 0.19));
        g.addEdge(new Edge(0, 2, 0.26));
        g.addEdge(new Edge(1, 2, 0.36));
        g.addEdge(new Edge(1, 3, 0.29));
        g.addEdge(new Edge(2, 7, 0.34));
        g.addEdge(new Edge(6, 2, 0.40));
        g.addEdge(new Edge(3, 6, 0.52));
        g.addEdge(new Edge(6, 0, 0.58));
        g.addEdge(new Edge(6, 4, 0.93));
        for (Edge edge : new Kruskal(g).edges()) {
            System.out.println(edge);
        }
    }

    private Queue<Edge> mst;
	private boolean weight;

    public Kruskal(UndirectedGraph g) {

        mst = new LinkedQueue<>();
        MinPQ<Edge> pq = new MinPQ<>();
        for (Edge edge : g.edges()) {
            pq.insert(edge);
        }
        UnionFind uf = new UnionFind(g.v());
        while (!pq.isEmpty() && mst.size() < g.v() - 1) {
            Edge edge = pq.delMin();
            int v = edge.either();
            int w = edge.other(v);
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.enqueue(edge);
				weight += edge.weight();
            }
        }
    }

    public Iterable<Edge> edges() {
        return mst;
    }
	
	public boolean weight() {
		return weight;
	}
}
